package 我的Java学习_算法基础.day_06;

public class _100_特殊的同余方程_逆元 {
    public static void main(String[] args) {
        //13x==1(%5)
        try{
            LinearEquation.inverseElement(13,5);
            System.out.println(LinearEquation.x);
        }catch (Exception e){
            System.out.println("无解");
        }

    }

    /**
     * 求逆元
     * ax%n=1
     */
    private static class LinearEquation {
        static long x;
        static long y;
        /**
         * 扩展欧几里得
         * 调用完成后x、y是ax+by=gcd(a,b)的解
         * @param a
         * @param b
         * @return 最大公约数
         */
        public static long ext_gcd(long a,long b){
            if(b==0){
                x=1;
                y=0;
                return a;
            }
            long res = ext_gcd(b,a%b);
            //x,y已经被下一层递归更新了
            long x1 = x;//备份x
            x=y;//更新x
            y=x1-a/b*y;//更新y
            return res;
        }
        /**
         * 求ax+by=m 的解
         * @param a
         * @param b
         * @param m
         * @throws Exception
         */
        public static long linearEquation(long a,long b,long m)throws Exception{
            long d = ext_gcd(a,b);
            //m不是gcd（a,b）的倍数，这个方程无解
            if(m%d!=0) throw new Exception("无解");
            long n = m/d;
            x*=n;
            y*=n;
            return d;
        }

        /**
         * 求逆元
         * ax%n=1中的x
         * @param a
         * @param mo
         * @return
         * @throws Exception
         */
        public static long inverseElement(long a,long mo) throws Exception{
            long d = LinearEquation.linearEquation(a,mo,1);
            x=(x%mo+mo)%mo;//保证x>0
            return d;
        }

    }
}
